//
// Description: 5955. 摘水果
// Created by Loading on 2021/12/12.
//

#include <bits/stdc++.h>

using namespace std;

int maxTotalFruits(vector<vector<int>> &fruits, int startPos, int k) {
    int n = fruits.size();
    int res = 0;
    // 前缀和，方便计算，错开增加一位，使用时需注意下标
    vector<int> pre(n + 1);
    for (int i = 1; i <= n; ++i) {
        pre[i] = pre[i - 1] + fruits[i - 1][1];
    }
    // 离散化，位置
    vector<int> pos;
    for (int i = 0; i < n; ++i) {
        pos.emplace_back(fruits[i][0]);
    }

    /* 假设向左走i步，返回，并又向右走j步，区间为[startPos - i, startPos + j]；反向同理 */
    for (int i = 0; i <= k / 2; ++i) {
        int j = k - 2 * i;
        // 先向左
        // 确定区间
        int l = startPos - i, r = startPos + j;
        /* 由于前缀和数组错开一位，所以左端点映射使用lower，右端点映射使用upper */
        int pos_l = lower_bound(pos.begin(), pos.end(), l) - pos.begin();
        int pos_r = upper_bound(pos.begin(), pos.end(), r) - pos.begin();
        res = max(res, pre[pos_r] - pre[pos_l]);
        // 先向右
        l = startPos - j;
        r = startPos + i;
        pos_l = lower_bound(pos.begin(), pos.end(), l) - pos.begin();
        pos_r = upper_bound(pos.begin(), pos.end(), r) - pos.begin();
        res = max(res, pre[pos_r] - pre[pos_l]);
    }

    return res;
}

int main() {
    vector<vector<int>> fruits = {{0,  9},
                                  {4,  1},
                                  {5,  7},
                                  {6,  2},
                                  {7,  4},
                                  {10, 9}};
    int startPos = 5;
    int k = 4;
    int res = maxTotalFruits(fruits, startPos, k);
    cout << res << endl;

    return 0;
}